#include <stdio.h>
#include "convex.h"

// 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product.
// Returns a positive value, if OAB makes a counter-clockwise turn,
// negative for clockwise turn, and zero if the points are collinear.
coord2_t cross(const point_t O, const point_t A, const point_t B)
{
        return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

void convex_hull(int N, point_t *P, point_t *H)
{
	/* ai: instruction "convex_hull" is entered with @N = 20; */
	int i = 0;
	int j = 0;
	int k = 0;
	int t = 0;

	int res_k = 0;
	int res_cross = 0;
	int cancel = 0;

  //first two points static in the convex hull
	H[k++] = P[i++];
	H[k++] = P[i++];	

	// Build lower hull
    for (i = 2; i < N; i++) 
	{
		cancel = 0;

		for(j=0; j <= N-2; j++)
		{
			res_k = (k >= 2 ? 1 : 0);

			res_cross = ((cross(H[k-2], H[k-1], P[i]) <= 0) ? 1 : 0);
			k = ((res_k && res_cross && !cancel) ? k-1 : k);
			cancel = ((res_k > 0) && (res_cross > 0) && (cancel == 0)) ? 0 : 1;
		}
		H[k++] = P[i];
    }

	i=N-2;
  //first point static in the convex hull
	H[k++] = P[i];	

    // Build upper hull
    for (i = N-3, t = k; i >= 0; i--) 
	{
		cancel = 0;

		for(j=0; j <= N-1; j++)
		{
			res_k = (k >= t ? 1 : 0);

			res_cross = ((cross(H[k-2], H[k-1], P[i]) <= 0) ? 1 : 0);
			k = ((res_k && res_cross && !cancel) ? k-1 : k);
			cancel = ((res_k > 0) && (res_cross > 0) && (cancel == 0)) ? 0 : 1;

		}
    	H[k++] = P[i];
    }
}
